package demo150;

import java.util.*;

public class GetMedian {
    /**
     * 插入排序
     */
    List<Integer> nums1 = new ArrayList<>();
    public  void Insert1(Integer num) {
        nums.add(num);
        insertSort(num);

    }

    public  Double GetMedian1() {
        int n = nums.size();
        double sum = 0;
        if (n % 2 == 0) {
            sum += nums.get(n / 2);
            sum += nums.get((n / 2) - 1);
            return sum / 2;
        }

        return (double)nums.get(n / 2);
    }

    public void insertSort(int tart) {
        int n = nums.size();
        int i = n-1;
        for(;i >0;i--) {
            if(nums.get(i-1) < tart) {
                break;
            }
            nums.set(i,nums.get(i-1));
        }
        nums.set(i,tart);
    }



    /**
     * 快速排序
     */
    List<Integer> nums = new ArrayList<>();
    public void Insert(Integer num) {
        nums.add(num);
        quickSort(0, nums.size()-1);

    }

    public Double GetMedian() {
        int n = nums.size();
        double sum = 0;
        if (n % 2 == 0) {
            sum += nums.get(n / 2);
            sum += nums.get((n / 2)-1);
            return sum / 2;
        }

        return (double)nums.get(n / 2);
    }

    public void quickSort(int start, int end) {
        if (start < end) {
            int base = nums.get(start);
            int left = start;
            int right = end;
            while (left < right) {
                //从右往左找比base小的数
                while (left < right && nums.get(right) >= base) {
                    right--;
                }
                nums.set(left, nums.get(right));
                //从左往右找比base大的数
                while (left < right && nums.get(left) <= base) {
                    left++;
                }
                nums.set(right, nums.get(left));

                nums.set(left, base);
                quickSort(start, left - 1);
                quickSort(left + 1, end);
            }
        }

    }

}
